package com.leetcode.algorithm.y19.m04;

/**
 * leetcode-cn.com
 * (done)75. 颜色分类
 * @author: jie.deng
 * @time: 2019年4月19日 上午10:43:06
 */
public class MySolution0422 {
    
    /**
     * 75. 颜色分类
     * 
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * 
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 
     * 注意:
     * 不能使用代码库中的排序函数来解决这道题。
     * 
     * 示例:
     * 
     * 输入: [2,0,2,1,1,0]
     * 输出: [0,0,1,1,2,2]
     * 进阶：
     * 
     * 一个直观的解决方案是使用计数排序的两趟扫描算法。
     * 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
     * 你能想出一个仅使用常数空间的一趟扫描算法吗？
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 解题思路:
        // 设置三个 lt, gt, i 定义：nums[0...lt) == 0，nums[lt+1...i-1] = 1，nums(gt...n-1] == 2，遍历一遍改数列保持这个定义。
        int len = nums.length;
        int lt = 0;
        int gt = len - 1;
        while (lt <= gt && nums[lt] == 0) {
            lt++;
        }
        while (lt <= gt && nums[gt] == 2) {
            gt--;
        }
        int idx = lt;
        while (idx <= gt) {
            if (nums[idx] == 2) {
                // 交换
                nums[idx] = nums[gt];
                nums[gt--] = 2;
                while (idx <= gt && nums[gt] == 2) {
                    gt--;
                }
            }
            if (nums[idx] == 0) {
                nums[idx] = nums[lt];
                nums[lt++] = 0;
            }
            idx++;
        }
    }
}
